{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Subarrays Distinct Element Sum of Squares I"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: sumCounts"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #子数组不同元素数目的平方和 I"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong>&nbsp;开始的整数数组&nbsp;<code>nums</code>&nbsp;。</p>\n",
    "\n",
    "<p>定义 <code>nums</code>&nbsp;一个子数组的 <strong>不同计数</strong>&nbsp;值如下：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>令&nbsp;<code>nums[i..j]</code>&nbsp;表示 <code>nums</code> 中所有下标在 <code>i</code> 到 <code>j</code> 范围内的元素构成的子数组（满足 <code>0 &lt;= i &lt;= j &lt; nums.length</code> ），那么我们称子数组&nbsp;<code>nums[i..j]</code>&nbsp;中不同值的数目为&nbsp;<code>nums[i..j]</code>&nbsp;的不同计数。</li>\n",
    "</ul>\n",
    "\n",
    "<p>请你返回 <code>nums</code>&nbsp;中所有子数组的 <strong>不同计数</strong>&nbsp;的 <strong>平方</strong>&nbsp;和。</p>\n",
    "\n",
    "<p>由于答案可能会很大，请你将它对&nbsp;<code>10<sup>9</sup> + 7</code>&nbsp;<strong>取余</strong>&nbsp;后返回。</p>\n",
    "\n",
    "<p>子数组指的是一个数组里面一段连续 <strong>非空</strong>&nbsp;的元素序列。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [1,2,1]\n",
    "<b>输出：</b>15\n",
    "<b>解释：</b>六个子数组分别为：\n",
    "[1]: 1 个互不相同的元素。\n",
    "[2]: 1 个互不相同的元素。\n",
    "[1]: 1 个互不相同的元素。\n",
    "[1,2]: 2 个互不相同的元素。\n",
    "[2,1]: 2 个互不相同的元素。\n",
    "[1,2,1]: 2 个互不相同的元素。\n",
    "所有不同计数的平方和为 1<sup>2</sup> + 1<sup>2</sup> + 1<sup>2</sup> + 2<sup>2</sup> + 2<sup>2</sup> + 2<sup>2</sup> = 15 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [2,2]\n",
    "<b>输出：3</b>\n",
    "<strong>解释：</strong>三个子数组分别为：\n",
    "[2]: 1 个互不相同的元素。\n",
    "[2]: 1 个互不相同的元素。\n",
    "[2,2]: 1 个互不相同的元素。\n",
    "所有不同计数的平方和为 1<sup>2</sup> + 1<sup>2</sup> + 1<sup>2</sup> = 3 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 100</code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 100</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [subarrays-distinct-element-sum-of-squares-i](https://leetcode.cn/problems/subarrays-distinct-element-sum-of-squares-i/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [subarrays-distinct-element-sum-of-squares-i](https://leetcode.cn/problems/subarrays-distinct-element-sum-of-squares-i/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,1]', '[1,1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        res = 0\n",
    "        for i in range(len(nums)):\n",
    "            record = [nums[i]]\n",
    "            num = 1\n",
    "            res += num**2\n",
    "            for j in range(i+1, len(nums)):\n",
    "                if nums[j] not in record:\n",
    "                    record.append(nums[j])\n",
    "                    num += 1\n",
    "                res += num**2\n",
    "        return res\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        res=0\n",
    "        n=len(nums)\n",
    "        for i in range(n):\n",
    "            hashmap=set()\n",
    "            for j in range(i,n):\n",
    "                hashmap.add(nums[j])\n",
    "                res+=len(hashmap)**2\n",
    "        Mod=10**9+7\n",
    "        return res%Mod\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        num=0\n",
    "        for i in range(len(nums)):\n",
    "            s=set()\n",
    "            for j in range(i,len(nums)):\n",
    "                s.add(nums[j])\n",
    "                num+=len(s)**2\n",
    "        return num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        total = [0]*len(nums)\n",
    "        last = dict()\n",
    "        res = 0\n",
    "        sum_ = 0\n",
    "        for i, num in enumerate(nums):\n",
    "            for j in range(i, last.get(num, -1), -1):\n",
    "                sum_ += 2*total[j] +1\n",
    "                total[j] += 1\n",
    "                sum_ %= 10**9 + 7\n",
    "            res = (res+sum_)%(10**9 + 7)\n",
    "            last[num] = i\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n == 1: return 1\n",
    "        if n == 0: return 0\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i, n):\n",
    "                ans += len(list(set(nums[i: j + 1]))) ** 2\n",
    "        return ans % (10 ** 9 + 7)\n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "\n",
    "        n = len(nums)\n",
    "        mod = 10**9 + 7\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            pre = set()\n",
    "            for j in range(i, n):\n",
    "                pre.add(nums[j])\n",
    "                ans += len(pre)**2\n",
    "                ans %= mod\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            m = {}\n",
    "            # if nums[i] in m:\n",
    "            #     m[nums[i]] += 1\n",
    "            # else:\n",
    "            #     m[nums[i]] = 1\n",
    "            for j in range(i,n):\n",
    "                if nums[j] in m:\n",
    "                    m[nums[j]] += 1\n",
    "                else:\n",
    "                    m[nums[j]] = 1\n",
    "                k = len(m)\n",
    "                ans += k*k\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            for j in range(i, n+1):\n",
    "                t = set(nums[i:j])\n",
    "                ans += len(t) ** 2\n",
    "                ans %= MOD\n",
    "        \n",
    "        return ans % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int: \n",
    "\n",
    "        # brute force \n",
    "\n",
    "        res = 0 \n",
    "        for i in range(len(nums)): \n",
    "            length = set() \n",
    "            for j in range(i, len(nums)): \n",
    "                length.add(nums[j]) \n",
    "                res += len(length)**2 \n",
    "        return res \n",
    "\n",
    "\n",
    "\n",
    "        '''\n",
    "        作者：cheturtle\n",
    "        链接：https://leetcode.cn/problems/subarrays-distinct-element-sum-of-squares-i/solutions/2502719/python-bao-li-qiong-ju-124ms-by-nrib8zib-r0xu/\n",
    "        '''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n == 1: return 1\n",
    "        if n == 0: return 0\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            hash = set()\n",
    "            cur_size = 0\n",
    "            for j in range(i, n):\n",
    "                if nums[j] not in hash:\n",
    "                    hash.add(nums[j])\n",
    "                    cur_size += 1\n",
    "                ans += cur_size ** 2\n",
    "        return ans % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i, n):\n",
    "                ans += len(list(set(nums[i: j+1])))**2\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        sum=0\n",
    "        mod=10**9+7\n",
    "        for i in range(0,n):\n",
    "            for j in range(0,n+1):\n",
    "                m=dict()\n",
    "                for k in range(i,j):\n",
    "                    m[nums[k]]=1\n",
    "                sum=(sum+len(m)*len(m))%mod\n",
    "        return sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        n, ans = len(nums), 0\n",
    "        for i in range(n + 1):\n",
    "            for j in range(i + 1, n + 1):\n",
    "                ans = (ans + len(set(nums[i : j])) ** 2) % 1000000007\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        MOD = 10 ** 9 + 7\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            st = set()\n",
    "            for j in range(i, n):\n",
    "                st.add(nums[j])\n",
    "                sz = len(st)\n",
    "                ans += sz * sz\n",
    "        return ans % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int: \n",
    "\n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "\n",
    "        def count(s:List[int]) -> int:\n",
    "            cnt = Counter()\n",
    "            result = 0\n",
    "            for num in s:\n",
    "                cnt[str(num)] += 1\n",
    "                if cnt[str(num)] > 1:\n",
    "                    continue;\n",
    "                else:\n",
    "                    result += 1\n",
    "            return result\n",
    "            \n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                s = nums[i:j+1:1]\n",
    "                ans += count(s) * count(s)\n",
    "        \n",
    "        return int(ans % (1e9 + 7))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for l in range(1, n+1):\n",
    "            for i in range(n):\n",
    "                end = i + l\n",
    "                if end > n:\n",
    "                    break\n",
    "                s = set(nums[i:end])\n",
    "                ans += len(s) ** 2\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for start in range(n):\n",
    "            for end in range(start+1, n+1):\n",
    "                s = set()\n",
    "                for index in range(start, end):\n",
    "                    s.add(nums[index])                     \n",
    "                ans += len(s) * len(s)\n",
    "        return ans % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        MOD = 1000000007\n",
    "        res = 0\n",
    "        for start in range(len(nums)):\n",
    "            for end in range(start, len(nums)):\n",
    "                tmp = len(set(nums[start:end + 1]))\n",
    "                res += tmp * tmp\n",
    "                res %= MOD\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        m = 10 ** 9 + 7\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            ans += 1\n",
    "            st = set([nums[i]])\n",
    "            for j in range(i + 1, n):\n",
    "                st.add(nums[j])\n",
    "                ans += len(st) ** 2\n",
    "                ans %= m\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        ans=0\n",
    "        for i in range(len(nums)):\n",
    "            s=set()\n",
    "            for j in range(i,len(nums)):\n",
    "                s.add(nums[j])\n",
    "                ans+=len(s)**2\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "        mod = 10 ** 9 + 7\n",
    "        for i in range(n):\n",
    "            s = set()\n",
    "            for j in range(i, n):\n",
    "                s.add(nums[j])\n",
    "                ans += len(s) ** 2 % mod\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def check(sub_nums: List[int]) -> int:\n",
    "    num_set = set()\n",
    "    for i in sub_nums:\n",
    "        num_set.add(i)\n",
    "    return len(num_set)\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        l = len(nums)\n",
    "        res = 0\n",
    "        for i in range(l):\n",
    "            for j in range(i+1,l+1):\n",
    "                # print(nums[i:j])\n",
    "                res = ( res + check(nums[i:j]) ** 2 ) % (10 ** 9 + 7)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        ret = 0\n",
    "        for i,x in enumerate(nums):\n",
    "            s = {x}\n",
    "            ret += 1\n",
    "            for y in nums[i+1:]:\n",
    "                s.add(y)\n",
    "                ret = (ret + len(s)**2) % 1000000007\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        cnt = 0\n",
    "        \n",
    "        for i in range(len(nums)):\n",
    "            for j in range(i, len(nums)):\n",
    "                cnt = (cnt + len(set(nums[i: j+1])) ** 2) % MOD\n",
    "        return cnt\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        ans=0\n",
    "        for i in range(len(nums)):\n",
    "            s=set()\n",
    "            for j in range(i,len(nums)):\n",
    "                s.add(nums[j])\n",
    "                ans+=len(s)**2\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        sumCount = 0\n",
    "        for w in range(1, len(nums)+1):\n",
    "            for i in range(len(nums)-w+1):\n",
    "                sumCount += len(set(nums[i:i+w]))**2\n",
    "        return sumCount"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        \"\"\"暴力\"\"\"\n",
    "        n = len(nums)\n",
    "        mod = 10**9+7\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            s = set()\n",
    "            for j in range(i,n):\n",
    "                s.add(nums[j])\n",
    "                ans += len(s)**2\n",
    "        return ans % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        return sum(pow(len(set(nums[i: j])), 2) for i in range(len(nums)) for j in range(i + 1, len(nums) + 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        res = 0\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(i + 1):\n",
    "                res += len(set(nums[j: i+1])) ** 2\n",
    "            res %= mod\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i, n):\n",
    "                res += len(Counter(nums[i:j + 1]).keys()) ** 2\n",
    "        \n",
    "        return res % (10 ** 9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        MOD = 10 ** 9 + 7\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            s = set()\n",
    "            for j in range(i, n):\n",
    "                s.add(nums[j])\n",
    "                ans = (ans + len(s) ** 2) % MOD\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        for i in range(len(nums)):\n",
    "            s=set()\n",
    "            for j in range(i,len(nums)):\n",
    "                s.add(nums[j])\n",
    "                ans+=len(s)**2\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = n\n",
    "        for i in range(n-1):\n",
    "            items = set()\n",
    "            items.add(nums[i])\n",
    "            for j in  range(i+1, n):\n",
    "                items.add(nums[j])\n",
    "                ans += len(items) ** 2\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        MOD = 10**9+7\n",
    "        n = len(nums)\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            for j in range(0, n-i):\n",
    "                res += len(Counter(nums[j:i+j+1]))**2\n",
    "                # print(Counter(nums[j:i+j+1]), res)\n",
    "        return res%MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        MOD = 10 ** 9 + 7\n",
    "        for i in range(n):\n",
    "            for j in range(i, n):\n",
    "                ans += len(set(nums[i:j+1])) ** 2\n",
    "                ans %= MOD\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i, n):\n",
    "                f = Counter(nums[i: j+1])\n",
    "                ans += len(f)**2\n",
    "        return ans % mod "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        ans=0\n",
    "        k=len(nums)\n",
    "        for i in range(k):\n",
    "            s=set()\n",
    "            for j in range(i,k):\n",
    "                s.add(nums[j])\n",
    "                ans+=len(s)**2\n",
    "        return ans%1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        l = len(nums)\n",
    "        ans = 0\n",
    "        for lenth in range(2,l+1):\n",
    "            for idx in range(l-lenth+1):\n",
    "                ans += len(set(nums[idx:idx+lenth])) ** 2\n",
    "        return ans + l "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        n, ans = len(nums), 0\n",
    "        for i in range(n + 1):\n",
    "            for j in range(i + 1, n + 1):\n",
    "                ans = (ans + len(set(nums[i : j])) ** 2) % 1000000007\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        sumCount = 0\n",
    "        for w in range(1, len(nums)+1):\n",
    "            for i in range(len(nums)-w+1):\n",
    "                sumCount += len(set(nums[i:i+w]))**2\n",
    "        return sumCount"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        n, ans = len(nums), 0\n",
    "        for i in range(n + 1):\n",
    "            for j in range(i + 1, n + 1):\n",
    "                ans = (ans + len(set(nums[i : j])) ** 2) % 1000000007\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        M = 10 ** 9 + 7\n",
    "        s = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i,n):\n",
    "                temp = nums[i:j+1]\n",
    "                # print(temp)\n",
    "                s += len(set(temp)) ** 2\n",
    "        return s % M\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            s = set()\n",
    "            for j in range(i, n):\n",
    "                s.add(nums[j])\n",
    "                ans += len(s) ** 2\n",
    "                ans %= MOD\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            seen = set()\n",
    "            for j in range(i, n):\n",
    "                seen.add(nums[j])\n",
    "                ans += len(seen)**2\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        sumCount = 0\n",
    "        for w in range(1, len(nums)+1):\n",
    "            for i in range(len(nums)-w+1):\n",
    "                sumCount += len(set(nums[i:i+w]))**2\n",
    "        return sumCount"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        for i in range(len(nums)):\n",
    "            s = set()\n",
    "            for j in range(i, len(nums)):\n",
    "                s.add(nums[j])\n",
    "                ans += len(s)**2\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        l = len(nums)\n",
    "        ans = 0\n",
    "        for lenth in range(2,l+1):\n",
    "            for idx in range(l-lenth+1):\n",
    "                ans += len(set(nums[idx:idx+lenth])) ** 2\n",
    "        return ans + l "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i, n):\n",
    "                ans += (len(set(nums[i: j + 1])) ** 2) % (10 ** 9 + 7)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class RangeAddRangeSum:\n",
    "\n",
    "    def __init__(self, n: int) -> None:\n",
    "        self.n = n\n",
    "        self.t1 = [0] * (n + 1)\n",
    "        self.t2 = [0] * (n + 1)\n",
    "        return\n",
    "\n",
    "    @staticmethod\n",
    "    def _lowest_bit(x: int) -> int:\n",
    "        return x & (-x)\n",
    "\n",
    "    def build(self, nums: List[int]) -> None:\n",
    "        assert len(nums) == self.n\n",
    "        for i in range(self.n):\n",
    "            self.range_add(i + 1, i + 1, nums[i])\n",
    "        return\n",
    "\n",
    "    def get(self) -> List[int]:\n",
    "        nums = [0] * self.n\n",
    "        for i in range(self.n):\n",
    "            nums[i] = self.range_sum(i + 1, i + 1)\n",
    "        return nums\n",
    "\n",
    "    # 更新单点的差分数值\n",
    "    def _add(self, k: int, v: int) -> None:\n",
    "        # start from index 1 and v can be any integer\n",
    "        v1 = k * v\n",
    "        while k <= self.n:\n",
    "            self.t1[k] = self.t1[k] + v\n",
    "            self.t2[k] = self.t2[k] + v1\n",
    "            k = k + self._lowest_bit(k)\n",
    "        return\n",
    "\n",
    "    def _sum(self, t: List[int], k: int) -> int:\n",
    "        # index start from 1 and query the sum of prefix k number\n",
    "        ret = 0\n",
    "        while k:\n",
    "            ret = ret + t[k]\n",
    "            k = k - self._lowest_bit(k)\n",
    "        return ret\n",
    "\n",
    "    def range_add(self, left: int, right: int, v: int) -> None:\n",
    "        # index start from 1 and v van be any integer\n",
    "        self._add(left, v)\n",
    "        self._add(right + 1, -v)\n",
    "        return\n",
    "\n",
    "    # 求数组的前缀区间和\n",
    "    def range_sum(self, left: int, right: int) -> int:\n",
    "        # index start from 1 and query the sum(nums[left-1: right]) which is 0-index array\n",
    "        a = (right + 1) * self._sum(self.t1, right) - self._sum(self.t2, right)\n",
    "        b = left * self._sum(self.t1, left - 1) - self._sum(self.t2, left - 1)\n",
    "        return a - b\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "\n",
    "        n = len(nums)\n",
    "        mod = 10**9 + 7\n",
    "        ans = dp = 0\n",
    "        dct = dict()\n",
    "        tree = RangeAddRangeSum(n)\n",
    "        for i in range(n):\n",
    "            num = nums[i]\n",
    "            if num not in dct:\n",
    "                dp += 2*tree.range_sum(1, i+1) + i+1\n",
    "                tree.range_add(1, i+1, 1)\n",
    "\n",
    "            else:\n",
    "                j = dct[num]\n",
    "                dp += 2*tree.range_sum(j+2, i+1) + i-j\n",
    "                tree.range_add(j+2, i+1, 1)\n",
    "            ans += dp\n",
    "            dct[num] = i\n",
    "            ans %= mod\n",
    "            dp %= mod\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        diffNum = []\n",
    "        result = 0\n",
    "        for i in range(len(nums)):\n",
    "            for e in range(len(nums)-i):\n",
    "                numList = nums[i:e+1+i]\n",
    "                data = list(set(numList))\n",
    "                diffNum.append(len(data))\n",
    "        for num in diffNum:\n",
    "            result += (num**2)\n",
    "        return result\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "\n",
    "        mod = 10**9+7\n",
    "\n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                d = Counter(nums[i:j+1])\n",
    "                ans += len(d)**2\n",
    "        return ans \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Fenwick_Tree:\n",
    "    def __init__(self, Maxsize):\n",
    "        self.tr = [0] * Maxsize\n",
    "        self.size = Maxsize\n",
    "\n",
    "    def add(self, pos, val):\n",
    "        while pos < self.size:\n",
    "            self.tr[pos] += val\n",
    "            pos += pos & (-pos)\n",
    "\n",
    "    def query(self, pos):\n",
    "        res = 0\n",
    "        while pos > 0:\n",
    "            res += self.tr[pos]\n",
    "            pos -= pos & (-pos)\n",
    "        return res\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, a: list[int]) -> int:\n",
    "        n = len(a)\n",
    "        tr0, tr1 = Fenwick_Tree(n + 4), Fenwick_Tree(n + 4)\n",
    "\n",
    "        def update(l: int, r: int, val: int):\n",
    "            tr0.add(l, val)\n",
    "            tr1.add(l, val * l)\n",
    "            tr0.add(r + 1, -val)\n",
    "            tr1.add(r + 1, -val * (r + 1))\n",
    "\n",
    "        def query(l: int, r: int):\n",
    "            res1 = (r + 1) * tr0.query(r) - l * tr0.query(l - 1)\n",
    "            res2 = tr1.query(r) - tr1.query(l - 1)\n",
    "            return res1 - res2\n",
    "\n",
    "        s_2 = [0] * (n + 1)\n",
    "        d = dict()\n",
    "        for i, x in enumerate(a, 1):\n",
    "            last = d.get(x, 0)\n",
    "            res = query(last + 1, i)\n",
    "            gain = i - last + 2 * res\n",
    "            update(last + 1, i, 1)\n",
    "            s_2[i] = s_2[i - 1] + gain\n",
    "            d[x] = i\n",
    "        return sum(s_2) % int(1e9 + 7)\n",
    "\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    pass\n",
    "    print(Solution.sumCounts(None, [1, 2, 1]))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List, Tuple, Optional\n",
    "from collections import defaultdict, Counter\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "\n",
    "MOD = int(1e9 + 7)\n",
    "INF = int(1e20)\n",
    "\n",
    "# 给你一个下标从 0 开始的整数数组 nums 。\n",
    "\n",
    "# 定义 nums 一个子数组的 不同计数 值如下：\n",
    "\n",
    "# 令 nums[i..j] 表示 nums 中所有下标在 i 到 j 范围内的元素构成的子数组（满足 0 <= i <= j < nums.length ），那么我们称子数组 nums[i..j] 中不同值的数目为 nums[i..j] 的不同计数。\n",
    "# 请你返回 nums 中所有子数组的 不同计数 的 平方 和。\n",
    "\n",
    "# 由于答案可能会很大，请你将它对 109 + 7 取余 后返回。\n",
    "\n",
    "\n",
    "# 子数组指的是一个数组里面一段连续 非空 的元素序列。\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        res = 0\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(i, len(nums)):\n",
    "                res += len(set(nums[i : j + 1])) ** 2\n",
    "        return res % MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i, n):\n",
    "                res += (len(Counter(nums[i:j+1]))) ** 2\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def sumCounts(self, nums: List[int]) -> int:\r\n",
    "        n = len(nums)\r\n",
    "        ans = 0\r\n",
    "        for l in range(1, n+1):\r\n",
    "            for i in range(n-l+1):\r\n",
    "                ans += len(set(nums[i:i+l]))** 2\r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        n = len(nums)\n",
    "        res = []\n",
    "\n",
    "        def sliding_window(nums, length):\n",
    "            hashmap = Counter(nums[:length])\n",
    "            res.append(len(hashmap))\n",
    "            for i in range(n - length):\n",
    "                hashmap[nums[i]] -= 1\n",
    "                if hashmap[nums[i]] == 0:\n",
    "                    del hashmap[nums[i]]\n",
    "                hashmap[nums[i+length]] += 1\n",
    "                res.append(len(hashmap))\n",
    "\n",
    "        for i in range(1, n + 1):\n",
    "            sliding_window(nums, i)\n",
    "\n",
    "        return sum(map(lambda x: x ** 2, res)) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        arr = []\n",
    "        MOD = 10**9 + 7\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            for j in range(len(arr)):\n",
    "                arr[j].add(nums[i])\n",
    "            arr.append(set([nums[i]]))\n",
    "            for a in arr:\n",
    "                res += (len(a))**2 % MOD\n",
    "        return res\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        def dict_jian(a,b):\n",
    "            ans = 0\n",
    "            for key in b:\n",
    "                if key not in a:\n",
    "                    ans += 1\n",
    "                elif b[key]>a[key]:\n",
    "                        ans += 1\n",
    "            return ans\n",
    "        n = len(nums)\n",
    "        cnt = collections.defaultdict(int)\n",
    "        cnts = [{}]\n",
    "        ans = 0\n",
    "        for num in nums:\n",
    "            cnt[num] += 1\n",
    "            cnts.append(cnt.copy())\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(i+1,n+1):\n",
    "                ans +=  dict_jian(cnts[i],cnts[j])**2\n",
    "        return ans % (10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        MOD = 10**9+7\n",
    "        #动态规划\n",
    "        n = len(nums)\n",
    "        res = 0\n",
    "        dp = [[0]*n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            dp[i][i]=1\n",
    "            res =(res + dp[i][i]*dp[i][i])%MOD\n",
    "            for j in range(i+1,n):\n",
    "                if nums[j] not in nums[i:j]:\n",
    "                    dp[i][j] = dp[i][j-1] + 1\n",
    "                    \n",
    "                else:\n",
    "                    dp[i][j] = dp[i][j-1]\n",
    "                res =(res + dp[i][j]*dp[i][j])%MOD\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self):\n",
    "        self.begin = 0\n",
    "        self.end = 0\n",
    "        self.sum = 0 #本段的所有数字的和,不算被上层盘剥的\n",
    "        self.cache = 0 # 对下层的盘剥次数\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "\n",
    "class SegTree:\n",
    "    def __init__(self,begin,end):\n",
    "        self.root = Node()\n",
    "        self.root.begin = begin\n",
    "        self.root.end = end\n",
    "    \n",
    "    def querySum(self,begin,end):\n",
    "        return self.internal_querySum(self.root,begin,end,0)\n",
    "\n",
    "    def update(self,begin,end):\n",
    "        return self.internal_update(self.root,begin,end)\n",
    "\n",
    "    def internal_querySum(self,node,begin,end,c):\n",
    "        if end<node.begin or begin>node.end:\n",
    "            return 0\n",
    "        if begin<=node.begin and end>=node.end:\n",
    "            return node.sum + (node.end-node.begin+1)*c\n",
    "\n",
    "        if node.left==None: #没有子层\n",
    "            mid = (node.begin+node.end)//2\n",
    "            \n",
    "            node.left = Node()\n",
    "            node.left.begin = node.begin\n",
    "            node.left.end = mid\n",
    "            node.left.sum = node.sum*(node.left.end-node.left.begin+1)//(node.end-node.begin+1)\n",
    "\n",
    "            node.right = Node()\n",
    "            node.right.begin = mid + 1\n",
    "            node.right.end = node.end\n",
    "            node.right.sum = node.sum*(node.right.end-node.right.begin+1)//(node.end-node.begin+1)\n",
    "\n",
    "        ret =  self.internal_querySum(node.left,begin,end,c+node.cache)\n",
    "        ret += self.internal_querySum(node.right,begin,end,c+node.cache)\n",
    "        return ret\n",
    "\n",
    "\n",
    "    def internal_update(self,node,begin,end):\n",
    "        if end<node.begin or begin>node.end:\n",
    "            return 0\n",
    "        if begin<=node.begin and end>=node.end:\n",
    "            node.sum += node.end-node.begin+1\n",
    "            node.cache += 1\n",
    "            return node.end-node.begin+1\n",
    "\n",
    "        if node.left==None: #没有子层\n",
    "            mid = (node.begin+node.end)//2\n",
    "\n",
    "            node.left = Node()\n",
    "            node.left.begin = node.begin\n",
    "            node.left.end = mid\n",
    "            node.left.sum = node.sum*(node.left.end-node.left.begin+1)//(node.end-node.begin+1)\n",
    "\n",
    "            node.right = Node()\n",
    "            node.right.begin = mid + 1\n",
    "            node.right.end = node.end\n",
    "            node.right.sum = node.sum*(node.right.end-node.right.begin+1)//(node.end-node.begin+1)\n",
    "\n",
    "        #打破本层 则本层的累积要下放\n",
    "\n",
    "\n",
    "        ret =  self.internal_update(node.left,begin,end)\n",
    "        ret += self.internal_update(node.right,begin,end)\n",
    "\n",
    "        node.sum += ret\n",
    "\n",
    "        return ret\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        ret = 0\n",
    "        d = {}\n",
    "        #需要[0,len(nums)-1]的线段树\n",
    "        ST = SegTree(0,len(nums)-1)\n",
    "        sqs = 0 #平方和\n",
    "        for i in range(len(nums)-1,-1,-1):\n",
    "            num = nums[i]\n",
    "\n",
    "            ni = d.get(num,len(nums))\n",
    "            d[num] = i\n",
    "\n",
    "            nsqs = sqs + ni - i\n",
    "            v = 0\n",
    "            if i+1<=ni-1:\n",
    "                v = ST.querySum(i+1,ni-1) #在线段树中查询[i+1,ni-1]的和\n",
    "            #print(i+1,ni-1,v)\n",
    "            nsqs += 2*v\n",
    "            #print(\"nsqs\",nsqs)\n",
    "            ST.update(i,ni-1)#在线段树中给区间[i,ni-1]加一\n",
    "\n",
    "            ret += nsqs\n",
    "            ret %= 1000000007\n",
    "            #print(\"ret\",ret)\n",
    "            sqs = nsqs\n",
    "        return ret\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        sum=0\n",
    "        leng = 1\n",
    "        def CheckIsDiff(nums,num):\n",
    "            ret = True\n",
    "            for n in nums:\n",
    "                if(n==num):\n",
    "                    ret = False\n",
    "            return ret\n",
    "        while(leng<=len(nums)):\n",
    "            for i in range(0,len(nums)-leng+1,1):\n",
    "                diffNum = 1\n",
    "                diffNums = [nums[i]]\n",
    "                for a in range(i,i+leng,1):\n",
    "                    if(CheckIsDiff(diffNums,nums[a])==True):\n",
    "                        diffNums.append(nums[a])\n",
    "                        diffNum+=1\n",
    "                print(diffNum)\n",
    "                sum+=diffNum**2\n",
    "            leng+=1\n",
    "        return sum%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumCounts(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        sum = [0] * (n * 4)\n",
    "        todo = [0] * (n * 4)\n",
    "\n",
    "        def do(o: int, l: int, r: int, add: int) -> None:\n",
    "            sum[o] += add * (r - l + 1)\n",
    "            todo[o] += add\n",
    "\n",
    "        # o=1  [l,r] 1<=l<=r<=n\n",
    "        # 把 [L,R] 加一，同时返回加一之前的区间和\n",
    "        def query_and_add1(o: int, l: int, r: int, L: int, R: int) -> int:\n",
    "            if L <= l and r <= R:\n",
    "                res = sum[o]\n",
    "                do(o, l, r, 1)\n",
    "                return res\n",
    "\n",
    "            m = (l + r) // 2\n",
    "            add = todo[o]\n",
    "            if add:\n",
    "                do(o * 2, l, m, add)\n",
    "                do(o * 2 + 1, m + 1, r, add)\n",
    "                todo[o] = 0\n",
    "\n",
    "            res = 0\n",
    "            if L <= m: res += query_and_add1(o * 2, l, m, L, R)\n",
    "            if m < R:  res += query_and_add1(o * 2 + 1, m + 1, r, L, R)\n",
    "            sum[o] = sum[o * 2] + sum[o * 2 + 1]\n",
    "            return res\n",
    "\n",
    "        ans = s = 0\n",
    "        last = {}\n",
    "        for i, x in enumerate(nums, 1):\n",
    "            j = last.get(x, 0)\n",
    "            s += query_and_add1(1, 1, n, j + 1, i) * 2 + i - j\n",
    "            ans += s\n",
    "            last[x] = i\n",
    "        return ans % 1_000_000_007\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
